Entscheidungsbaumverfahren

I

Entscheidungsbaumverfahren,

 

in der Regel computergestützte Verfahren des Operations Research zur Bestimmung optimaler Lösungen von Problemen, für die eine unüberschaubar große Anzahl aufeinander abzustimmender Teilentscheidungen mit jeweils unterschiedlichen Konsequenzen typisch ist. Die entsprechenden Teilprobleme werden in einem Baum dargestellt und der Lösungsprozess wird als ein speziellen Regeln folgendes Suchverfahren organisiert. Bei der Roll-back-Analyse startet das Suchverfahren in den Zweigenden des Baumes, schreitet zurück bis in dessen Wurzel und erfordert die Bewertung sämtlicher Entscheidungsalternativen. Bei der dynamischen Programmierung beginnt der Suchvorgang in der Baumwurzel; Zweige mit zulässigen (Teil-)Lösungen werden nur so weit entwickelt, bis erkennbar ist, dass sie nicht optimal sind. Es braucht daher nur eine Teilmenge aller Entscheidungsalternativen bewertet zu werden. Beim Branch-and-bound-Verfahren beginnt der Suchvorgang ebenfalls in der Baumwurzel, jedoch mit einer unzulässigen Lösung, die zuvor mit einer geeigneten Methode (z. B. der linearen oder der mathematischen Programmierung, Optimierung) erzeugt wurde. In den Zweigen des Entscheidungsbaums werden dann die Unzulässigkeiten schrittweise ausgeräumt, bis die zulässige und optimale Lösung erreicht ist. Auch hier braucht nur eine Teilmenge aller Entscheidungsalternativen bewertet zu werden.

II

Entscheidungsbaumverfahren,

 

in der Regel computergestützte Verfahren des Operations-Research zur Bestimmung optimaler Lösungen von Problemen, für die eine kombinatorisch große Anzahl aufeinander abzustimmender Teilentscheidungen mit jeweils unterschiedlichen Konsequenzen typisch ist. Stellt man die entsprechenden Teilprobleme mit ihren gegenseitigen Abhängigkeiten in geeigneter Weise grafisch dar, so erhält man einen Entscheidungsbaum (Baum), in dem der Lösungsprozess als speziellen Regeln folgendes Suchverfahren organisiert werden kann. Bei der Roll-back-Analyse startet das Suchverfahren in den Zweigenden des Baumes, schreitet zurück bis in dessen Wurzel und erfordert die Bewertung sämtlicher Entscheidungsalternativen (geeignet z. B. für die Lösung von Investitionsproblemen bei Ungewissheit). Bei der dynamischen Programmierung beginnt der Suchvorgang in der Baumwurzel; Zweige mit zulässigen (Teil-)Lösungen werden nur soweit entwickelt, bis deren Nichtoptimalität erkennbar ist. Es braucht daher nur eine Teilmenge aller Entscheidungsalternativen bewertet zu werden (Anwendung z. B. bei der Lösung mehrperiodiger Lagerhaltungsprobleme). Beim Branch-and-bound-Verfahren beginnt der Suchvorgang ebenfalls in der Baumwurzel, jedoch mit einer unzulässigen Lösung, die zuvor mit einer geeigneten Methode (z. B. der der linearen Programmierung, mathematische Programmierung) erzeugt wurde. In den Zweigen des Entscheidungsbaums werden dann die Unzulässigkeiten schrittweise ausgeräumt, bis die zulässige und optimale Lösung erreicht ist. Auch hier braucht nur eine Teilmenge aller Entscheidungsalternativen bewertet zu werden (Anwendung bei der Lösung von Standortbelegungsproblemen, von Aufgaben der ganzzahligen Programmierung u. a.).